Data Structure: Stack and Queue
Tags: muict, datastructure, stack, queue
Published: 2018-09-13 06:18:17

---
title: Data Structure: Stack and Queue
published: true
description: MUICT Data Structure's course; stack and queue
tags: MUICT, data structure, stack, queue
---

Stacks and Queues are often used as programmer's tools during the operation of a program and are usually deleted after the task is completed. 

## Stack 
A _stack_ is an abstract data structure that follows the "last-in-first-out" or _LIFO_ model. Some real world examples are the "click to go back" to the previous web page, and text editor's undo feature.

There are 3 basic operations on a stack:
        1. Push: Insert a data item on the stack.
        2. Pop: Remove an item from the top of the stack.
        3. Peek: Read the value of an item from the top of the stack WITHOUT removing it.
<a href="https://www.programiz.com/dsa/stack">![](https://thepracticaldev.s3.amazonaws.com/i/l8r4ic2gedi0j9obd7ix.jpg)</a>

In programming, you can implement a stack using an _array_ or a _linked list_. (below is an example of the implementation of a stack with java)

```java
class StackX {
    private int maxSize;
    private long[] stackArray;
    private int top;

    public StackX(int s) {                // constructor
        maxSize = s;                      // set the array size
        stackArray = new long[maxSize];   // create an array
        top = -1;                         // no items yet
    }
    
    public void push(long j) {        // put items on top of the stack
        stackArray[++top] = j;        // increment top when item inserted
    }
    public long pop() {               // take item from the top of the stack
        return stackArray[top--];     // access item, then decrement top
    }
    public long peek() {              // peek at the top of the stack
        return stackArray[top];
    }
    public boolean isEmpty() {        // true if the stack is empty
        return (top == -1);
    }
    public boolean isFull() {         // true if the stack is full
        return (top == maxSize -1);
    }
```

#### Stack Applications
- **reversing data**; e.g. reversing a string
- **parsing**: breaks the data into independent pieces for further provessing; e.g. Check the delimiter matching [,{,(,),},].
![](https://thepracticaldev.s3.amazonaws.com/i/7ms9fkqp5iboxpmsheky.png)

    > how it works:
    > - read characters from the string one at a time
    > - if you encounter an _opening delimiter_ [,{,(, place it on a stack
    > - if you encounter a _closing delimiter_, pop the item from the top of the stack 
    > - in case they don't match (the opening and closing delimiter), then an error occurs.

    for example: a{b(c[d]e)f}h

| String | Stack |
| ------ | ----- |
| a | empty |
|{ | { |
| b | { |
|( | {( |
| c | {( |
| [ | {([ |
| d | {([ |
| ] | {( |
| e | {( |
| ) | { |
| f | { |
| { | empty |
| h | empty |

- **postponing**: When the use of the data must be postponed for a while. For example, parsing an arithmetic expression; 3+(5-9)*4

    > Notations we're going to use: 
    > - prefix -> + a b
    > - infix -> a + b
    > - postfix a b +
    >
    > +, -, *, /, these are _operators_.
    > While we call the numbers (1,2,3,...) the _operands_.
    >
    > Precedence (priority, rank) relationships: 
    > - +, - have the same precedence
    > - *, / have the same precedence, and are higher than +, -

I figured that using a video to explain how it works should be easier, so here we go...
{% youtube z3VsmufB_QI%}
The reason we have to do this is because computers can only go either forward or backward through the expression. 

Let's look at how to convert the infix expression to the postfix one..
{% youtube vXPL6UavUeA %} 

And this is the video of how to evaluate the postfix expression..
{% youtube QCnANUfgC-w %}
    

For more detailed explanation, click <a href"http://interactivepython.org/runestone/static/pythonds/BasicDS/InfixPrefixandPostfixExpressions.html">here</a>.

- **backtracking**: used in many search applications, eight-queen problem, etc.
Example of finding a path:
{% youtube iaBEKo5sM7w %}
Example of n-queen problem:
{% youtube kX5frmc6B7c %}

## Queue
A _queue_ is an abstract data structure that follows "first-in-first-out" or _FIFO_ model. Some real world examples include printing a file (and there's a file in queue), process scheduler, a waiting line.

Basic operations on a queue:
    1. Enque/Add/Put: Insert a data item on the _back_ or rear of the queue.
    2. Deque/Delete/Get: Remove an item from the _front_ of the queue.
    3. Peek: Read the value of an item from the _front_ of the queue without removing it.

<a href"http://www.javascripttutorial.net/javascript-queue/">![](https://thepracticaldev.s3.amazonaws.com/i/fcxri84smzo9m1pxbxj9.png)</a>

Now, let's take a look at the implementation of a queue in java below!

```java
class Queue {
    private int maxSize;
    private long[] queArray;
    private int front;
    private int back;
    private int nItems;
    
    public Queue(int s) {                    // Constructor
        maxSize = s;
        quaArray = new long[maxSize];
        front = 0;
        back = -1;
        nItems = 0;
    }

    public void insert(long j) {            // Put an item at the back of the queue
        if(back == maxSize -1) back = -1;   // Deal with wraparound
        queArray[++back] = j;               // Increment back and insert the item
        nItems++;                           // One more item
    }
    public long remove() {                  // Take item from the front of the queue
        long temp = queArray[front++];      // Get the item and increment front
        if(front == maxSize) front = 0;     // Deal with wraparound
        nItems--;                           // One less item
        return temp;
    }
    public long peekFront() {
        return queArray[front];
    }
```

#### Queue in OS
When we have one processor, but there are many processes to be executed. To appear like the processes run simultaneously, we have to slice the CPU time into slots and create a queue that contains jobs to be executed.

#### Priority Queue
Items in the queue will be ordered (prioritized) by key value. There are 2 types of priority queue.
1. Ascending-priority queue - the item with the _smallest_ key has the highest priority
2. Descending-priority queue - the item with the _biggest_ key item has the highest priority

###### Inserting an item in priority queue : O(n)

Instead of inserting at the back or the rear of the queue, we insert the item based on its value compared to the others.

<a href="https://www.javamadesoeasy.com/2015/01/priority-queues.html">![](https://thepracticaldev.s3.amazonaws.com/i/70oy6oua9c6lehclupv8.png)</a>

####### Removing / Deleting the item : O(n)

Just like a normal queue, we remove the front one in the queue.

<a href="https://www.javamadesoeasy.com/2015/01/priority-queues.html">![](https://thepracticaldev.s3.amazonaws.com/i/653n0wuzd7chueckx7e5.png)</a>

------

That's the end of this post :) see you next time~