2.1 和队列的基本概念




2.1 和队列的基本概念

2.1 栈和队列的基本概念

  本质上是一种线性表,是只能在表的一端进行插入和删除操作的线性表。称表中允许插入和删除的一端为栈顶(top),不允许插入和删除的一端称为栈底(bottom)。如图2-1所示为一个顺序栈的示意图,其中栈底一直不变,而栈顶随着栈内元素的变化而变化,在顺序栈中永远指向下一个要写入的结点。
  入栈操作是指在栈顶插入元素的操作,出栈操作是指在栈顶删除元素的操作。栈是一种后进先出(LIFO)的数据结构,即后入栈的元素要比先入栈的元素先出栈。一串数据依次进入栈后,再依次出栈,那么出栈数据的次序将倒置。例如,线性表(2008,2009,2010,2011)中的元素依次全部入栈后,再全部出栈,那么出栈的次序为(2011,2010,2009,2008),如图2-2所示。
  队列本质上也是一种线性表,标准队列只能在一端插入数据元素,在另一端删除数据元素,只能删除元素的一端称为队列头或队头(front),只能插入元素的一端称为队列尾或队尾(rear)。向队列尾插入元素的操作称为入队列,从队列头删除元素的操作称为出队列。先入队列的数据也要先出队列,即队列是一种先进先出(FIFO)的数据结构,因此,队列并不能更改数据串的次序。如图2-3所示,数据串(1,2,3,…,n)依次进入一个队列,最后以相同的次序离开队列。

2.1 和队列的基本概念

发表评论

Contact

北京考研中心大厦

Connect

Subscribe

最新考研资料,欢迎联系博主获取。