Rangkuman Data Structure Session 6 (25 Februari 2020)

A. Outline:

  1. Stack Concept
  2. Infix, Prefix, Postfix Notation
  3. Stack Applications
  4. Queue Concept
  5. Circular Queue
  6. Priority Queue

B. Summary

1. Stack Concept

Stack is a linear data strucutre. That means the datas are organized sequentially or linearly. This kind of data structure is very easy to implement becasue memory of computer is also organized in linear fashion.

A stack is also called a LIFO (Last In First Out) data structure. It's much like an actual stack of plate. The last plate being placed is the first to be removed. 



Hasil gambar untuk LIFO plate
Stack has two variables:
  • TOP which is used to store the address of the topmost element of the stack
  • MAX which is used to store the maximum number of elements that the stack can hold

2. Infix, Prefix, Postfix Notation

Prefix
Infix
Postfix
* 4 10
4 * 10
4 10 *
+ 5 * 3 4
5 + 3 * 4
5 3 4 * +
+ 4 / * 6 – 5 2 3
4 + 6 * (5 – 2) / 3
4 6 5 2 – * 3 /  +









  • Prefix : operator is written before operands
  • Infix : operator is written between operands
  • Postfix : operator is written after operands

3. Stack Applications

  • Reverse the order of data
  • Converting a decimal number into its binary equivalent
  • Convert infix expression into postfix
  • Etc.

4. Queue Concept

A queue is a FIFO (First In First Out) data structure. That means the first data is going to be removed first. Imagine a line of people in a library. The first person to enter the line is going to get the book first.

Hasil gambar untuk movie theater queue data structure

5. Circular  Queue

Hasil gambar untuk circular queue

Circular Queue is a linear data structure in which the operations are performed based on FIFO (First In First Out) principle and the last position is connected back to the first position to make a circle.

In a Linear queue, once the queue is completely full, it’s not possible to insert more elements. Even if we dequeue the queue to remove some of the elements, until the queue is reset, no new elements can be inserted. This problem can be resolved by using Circular Queue

6. Priority Queue

A priority queue is a special type of queue in which each element is associated with a priority and is served according to its priority. If elements with the same priority occur, they are served according to their order in the queue.

For example: The element with the highest value is considered as the highest priority element.

Priority Queue
In a queue, the first-in-first-out rule is implemented whereas, in a priority queue, the values are removed on the basis of priority. The element with the highest priority is removed first.


SOURCE:


Komentar

Posting Komentar

Postingan Populer