栈的逻辑结构

Overview of the Packet Domain Logical Architecture：

Gf

Uu

Um D

Gi

Gn Iu Gc C E

Gp Gs

Signalling and Data Transfer Interface Signalling Interface MSC/VLR

TE MT UTRAN TE PDN Gr Iu HLR

Other PLMN SGSN

GGSN Gd SM-SC SMS-GMSC

SMS-IWMSC

GGSN

EIR SGSN Gn CGF Ga Ga

Billing

System Gb

TE MT BSS

R A

R CAMEL GSM-SCF

Ge

User Plane for GSM

RelayNetworkServiceGTP-UApplicationIPSNDCPLLCRLCMACGSM RFSNDCPLLCBSSGPL1bisRLCMACGSM RFBSSGPL1bisRelayL2L1IPL2L1IPGTP-UIPUmGbGnGiMSBSSSGSNGGSNNetworkServiceUDPUDP

Control Plane for SGSN – GGSN and SGSN – SGSN User Plane for SGSN – GGSN and SGSN – SGSN Interfaces：

UDP

L2

L1 IP

L2

L1 IP UDP

Gn or Gp

GSN GSN GTP-C GTP-C

UDP

L2

L1 IP

L2

L1 IP UDP

Gn or Gp

GSN GSN GTP-U GTP-U

User Plane for UMTS：

L1RLCPDCPMACE.g., IP,PPPApplicationL1RLCPDCPMACATMUDP/IPGTP-UAAL5RelayL1UDP/IPL2GTP-UE.g., IP,PPP3G-SGSNUTRANMSIu-PSUuGnGi3G-GGSNATMUDP/IPGTP-UAAL5L1UDP/IPGTP-UL2Relay

1

数据结构

第3章 栈与队列总结

栈 顺序栈 单链栈 循环链栈 双向链栈 双向循环链栈

数组 结构体

结构模型 #define

MAXSIZE 10

typedef struct{

SElemType

Stack[MAXSIZE];

int top;

}SeqStack; typedef struct{

SElemType *base;//在栈构造之前和销毁之后，base的值为NULL

SElemType *top;//栈顶指针

int

stacksize;//当前分配的存储空间，以元素为单位

}SqStack; typedef struct{

SElemType *base;//在栈构造之前和销毁之后，base的值为NULL

SElemType *top;//栈顶指针

int stacksize;//当前分配的存储空间，以元素为单位

}SqStack; struct CirNode

{

int data; //数据域

struct CirNode *next; //指针域

};

typedef CirNode *CirLinkList; struct DulNode

{

int data;

struct DulNode *prior;

struct DulNode *next;

};

typedef DulNode

*DulLinkList; 同双向链表 2

初始化(Init) void InitStack(SeqStack &S) //构造一个空栈S

{

S.top=-1; //top为下标

} void InitStack(SqStack &S)//构造一个空栈S

{

if(!(S.base=(SElemType

*)malloc(STACK_INIT_SIZE*sizeof(SElemType))))

exit(OVERFLOW);//存储分配失败

数据结构--栈和队列基础知识

⼀ 概述

栈和队列，严格意义上来说，也属于线性表，因为它们也都⽤于存储逻辑关系为 "⼀对⼀" 的数据，但由于它们⽐较特殊，因此将其单独作为⼀篇⽂

章，做重点讲解。既然栈和队列都属于线性表，根据线性表分为顺序表和链表的特点，栈也可分为顺序栈和链表，队列也分为顺序队列和链队列，这

些内容都会在本章做详细讲解。

使⽤栈结构存储数据，讲究“先进后出”，即最先进栈的数据，最后出栈；使⽤队列存储数据，讲究 "先进先出"，即最先进队列的数据，也最先出队

列。

⼆ 栈

2.1 栈的基本概念

同顺序表和链表⼀样，栈也是⽤来存储逻辑关系为 "⼀对⼀" 数据的线性存储结构，如下图所⽰。

从上图我们看到，栈存储结构与之前所了解的线性存储结构有所差异，这缘于栈对数据 "存" 和 "取" 的过程有特殊的要求：

1. 栈只能从表的⼀端存取数据，另⼀端是封闭的；

2. 在栈中，⽆论是存数据还是取数据，都必须遵循"先进后出"的原则，即最先进栈的元素最后出栈。拿图 1 的栈来说，从图中数据的存储状态可

判断出，元素 1 是最先进的栈。因此，当需要从栈中取出元素 1 时，根据"先进后出"的原则，需提前将元素 3 和元素 2 从栈中取出，然后才能

成功取出元素 1。

因此，我们可以给栈下⼀个定义，即栈是⼀种只能从表的⼀端存取数据且遵循 "先进后出" 原则的线性存储结构。通常，栈的开⼝端被称为栈顶；相应

地，封⼝端被称为栈底。因此，栈顶元素指的就是距离栈顶最近的元素，拿下图中的栈顶元素为元素 4；同理，栈底元素指的是位于栈最底部的元

素，下 中的栈底元素为元素 1。

2.2 进栈和出栈基于栈结构的特点，在实际应⽤中，通常只会对栈执⾏以下两种操作：

向栈中添加元素，此过程被称为"进栈"（⼊栈或压栈）；

从栈中提取出指定元素，此过程被称为"出栈"（或弹栈）；

2.3 栈的具体实现

栈是⼀种 "特殊" 的线性存储结构，因此栈的具体实现有以下两种⽅式：

1. 顺序栈：采⽤顺序存储结构可以模拟栈存储数据的特点，从⽽实现栈存储结构。使⽤顺序表模拟栈存储结构常⽤的实现思路，即在顺序表中设

栈的定义和特点

栈（stack）是⼀个特殊的线性表，是限定仅在⼀端（通常是表尾）进⾏插⼊和删除操作的线性表。

⼜称为后进先出（Last In First Out）的线性表，简称 LIFO 结构。

栈的相関概念：栈是仅在表尾进⾏插⼊、删除操作的线性表。

表尾（即an端）称为栈顶 Top；表头（即a1端）称为栈底 Base

例如：栈 s = (a1,a2,a3.....an-1,an) a1被称为栈底元素，an被称为栈顶元素

插⼊元素到栈顶（即表尾）的操作，称为⼊栈。

从栈顶（即表尾）删除最后⼀个元素的操作，称为出栈。

栈的⽰意图：

操作⽰意图-⼊栈：

操作⽰意图-出栈：

【思考】假设有3个元素a,b,c，⼊栈顺序是a,b,c 则他们的出栈顺序有⼏种可能

⼊栈顺序：a进⼊后，b进⼊，最后c进⼊

出栈顺序：（先进后出）所以得到，c,b,a这种出栈顺序

也可以：a⼊栈，接着a出栈；b⼊栈，接着b出栈；c⼊栈，接着c出栈。

还可以：a⼊栈，接着a出栈；b⼊栈，c⼊栈，接着c出栈，b出栈。

还可以：a⼊栈，b⼊栈，b出栈，a出栈，c⼊栈，c出栈

总结⼀下：

栈的定义：限定只能在表的⼀端进⾏插⼊和删除运算的线性表（只能在栈顶操作）

逻辑结构：与同线性表相同，仍为⼀对⼀关系。

存储结构：⽤顺序栈（⽤顺序存储的话，就叫顺序栈）或链栈（⽤链式存储的话，就叫链栈）存储均可，但以顺序栈更常见

运算规则：只能在栈顶运算，且访问结点时依照后进先出（LIFO）的原则

实现⽅式：关键是编写⼊栈和出栈函数，具体实现依顺序栈和链栈的不同⽽不同

栈与⼀般线性表的区别：仅在于运算规则不同。，

⼀般线性表

逻辑结构：⼀对⼀

存储结构：顺序表、链表

栈逻辑结构：⼀对⼀

存储结构：顺序栈、链栈