Biantian's Studio.

DS 02

DS
Word count: 170Reading time: 1 min
2020/04/13 Share

Stack & Queue

Stacks

Stack is an abstract data type, LIFOs (Last-In-First-Out).

1. Basic operation

  • push(x) = insert_beg
  • pop() = delete_beg
  • is_empty() = is_empty (for linked list)

2. Stacks as arrays

To avoid calling allocate_memory all the time, we need to know the maximum size of the stack in advance.

1
2
3
// Initialize an empty stack:
stack = new int[MAXSTACK];
stack_size = 0;

Queues

Queue is an abstract data type, FIFOs (First-In-First-Out)

1. Basic operation

  • enqueue(x)
  • dequeue()
  • is_empty()

2. Queue as a linked list

In this case, all operations take constant time.

  • enqueue = insert_end
  • dequeue = delete_beg

3. Queue stored in an array: Circular queue

1
2
3
4
// Initialize an empty queue:
queue = new int[MAXQUEUE];
front = 0;
size = 0;
1
2
3
4
5
6
7
8
9
10
boolean is_empty(){
    return size == 0;
}
void enqueue(int a){
    if(size == MAXQUEUE){
        throw OurOfMemoryException;	// the queue is full
    }
    queue[(front+size) mod MAXQUEUE] = a;
    size ++;
}

Other

1. div and mod

Note that a div b is always an integer and

(a div b)*b + a mod b = a.

Consequently: and

Author：Biantian

原文链接：http://biantian.github.io/2020/04/13/ds2/

发表日期：April 13th 2020, 9:30:51 am

更新日期：April 13th 2020, 11:10:38 am

版权声明：本文采用知识共享署名-非商业性使用 4.0 国际许可协议进行许可

CATALOG
  1. 1. Stack & Queue
    1. 1.1. Stacks
      1. 1.1.1. 1. Basic operation
      2. 1.1.2. 2. Stacks as arrays
    2. 1.2. Queues
      1. 1.2.1. 1. Basic operation
      2. 1.2.2. 2. Queue as a linked list
      3. 1.2.3. 3. Queue stored in an array: Circular queue
    3. 1.3. Other
      1. 1.3.1. 1. div and mod
Total : 12
2020
AI DB DS hashtable OSN hexo web note
Revision