Data Structure: Stack and Queue

#muict #datastructure #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.

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)

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 [,{,(,),},].
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...

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..

And this is the video of how to evaluate the postfix expression..

For more detailed explanation, click here.

backtracking: used in many search applications, eight-queen problem, etc. Example of finding a path: Example of n-queen problem:

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.

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

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.

Ascending-priority queue - the item with the smallest key has the highest priority
Descending-priority queue - the item with the biggest key item has the highest priority